
package Proyecto;

import java.util.ArrayList;


public class BusquedadProfundidadEvitandoCiclos {
    String estado[][];
    int nodosCreados,nodosExpandidos;
    long tiempoInicio,duracion;
    MonticuloBinarioDescendente arreglo;

    public BusquedadProfundidadEvitandoCiclos(String[][] estado) {
        this.estado = estado;
        nodosCreados=0;
        nodosExpandidos=0;
        arreglo=new MonticuloBinarioDescendente();
        arreglo.Ingresar(new Object[]{0,new Nodo(estado,0,null,null,0)});
    }

    public int RetornarNodosCreados()
    {
      return nodosCreados;
    }

    public int RetornarNodosExpandidos()
    {
      return nodosExpandidos;
    }
    
    public Nodo AlgoritmoBusquedadProfundidad()
    {
        Nodo actual=(Nodo) arreglo.ExtraerMax()[1];
        ArrayList <Nodo>hijos=new ArrayList<Nodo>();
        ArrayList <Nodo>recorridos=new ArrayList<Nodo>();
        if(actual.Viabilidad())
        { 
            while(!actual.EsMeta())
            {
                if(!recorridos.contains(actual)){
                    recorridos.add(actual);
                    hijos=actual.expandir();
                    nodosExpandidos++;
                    nodosCreados+=hijos.size();
                    for (int i = 0; i < hijos.size(); i++) {
                        Nodo hijo=(Nodo)hijos.get(i);                        
                        arreglo.Ingresar(new Object[]{hijo.profundidad,hijo});                
                    }
                    actual=(Nodo) arreglo.ExtraerMax()[1];                    
                }else actual=(Nodo)arreglo.ExtraerMax()[1];
            }
            duracion=System.currentTimeMillis()-tiempoInicio;
            System.out.println("Duracion :"+duracion);
            System.out.println("Meta hallada =D");
            return actual;
        }
        else return null;
    }
    
    
    
}
